package com.leetcode.linkedlist;

import com.leetcode.datastructure.ListNode;

/**
 * @author: ZhouBert
 * @date: 2019/10/1
 * @description:		19. 删除链表的倒数第N个节点
 * B
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 *
 * 示例：
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 * 说明：
 * 给定的 n 保证是有效的。
 *
 * 进阶：
 * 你能尝试使用一趟扫描实现吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class RemoveNthFromEnd19 {

	/**
	 * 使用双指针-一趟扫描
	 * todo:0 ms
	 * todo:思维上还可以优化一下。可以先确定慢指针！
	 * @param head
	 * @param n
	 * @return
	 */
	public static ListNode removeNthFromEnd(ListNode head, int n) {
		if (head==null||head.next==null){
			return null;
		}

		///后续出发的节点-最后可以到达删除节点的前一个节点
		ListNode laterNode=null;
		ListNode cur=head;
		int count=0;
		while (cur!=null){
			cur=cur.next;
			if (count>=n){
				if (count==n){
					laterNode=head;
				}else {
					laterNode=laterNode.next;
				}
			}
			count++;
		}
		ListNode temp =null;
		if (laterNode!=null){
			temp = laterNode.next;
			laterNode.next=laterNode.next.next;
			temp.next=null;

		}
		///删除第一个节点
		else{
			temp=head;
			head=head.next;
			temp.next=null;
		}
		return head;
	}

	public static void main(String[] args) {
		ListNode node5 = new ListNode(5);
		ListNode node4 = new ListNode(4);
		node4.next=node5;
		ListNode node3 = new ListNode(3);
		node3.next=node4;
		ListNode node2 = new ListNode(2);
		node2.next=node3;
		ListNode node1 = new ListNode(1);
		node1.next=node2;


		ListNode node3_2 = new ListNode(3);
		ListNode node2_2 = new ListNode(2);
		node2_2.next=node3_2;
		ListNode node1_2 = new ListNode(1);
		node1_2.next=node2_2;
		ListNode listNode = removeNthFromEnd(node1_2, 3);
		ListNode.print(listNode);
	}
}
